package labuladong.leetcode.editor.cn._04dp.ch00;

public class _509_FibonacciNumber {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /* 递归解 */
        public int fib1(int n) {
            if (n == 1 || n == 2) return 1;
            return fib1(n - 1) + fib1(n - 2);
        }

        /* 带备忘录的递归解法 */
        public int fib(int n) {
            // 备忘录全初始化为 0
            int[] memo = new int[n + 1];
            // 进行带备忘录的递归
            return helper(memo, n);
        }

        int helper(int[] memo, int n) {
            // base case
            if (n == 0 || n == 1) return n;
            // 已经计算过，不用再计算了
            if (memo[n] != 0) return memo[n];
            memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
            return memo[n];
        }

        /* dp 数组的迭代（递推）解法*/
        public int fib3(int n) {
            if (n == 0) return 0;
            int[] dp = new int[n + 1];
            // base case
            dp[0] = 0;
            dp[1] = 1;
            // 状态转移
            for (int i = 2; i <= n; i++) {
                dp[i] = dp[i - 1] + dp[i - 2];
            }
            return dp[n];
        }

        /* 存储之前的两个状态解法, 此方法最优*/
        public int fib4(int n) {
            if (n == 0 || n == 1) {
                // base case
                return n;
            }
            // 分别代表 dp[i - 1] 和 dp[i - 2]
            int dp_i_1 = 1, dp_i_2 = 0;
            for (int i = 2; i <= n; i++) {
                // dp[i] = dp[i - 1] + dp[i - 2];
                int dp_i = dp_i_1 + dp_i_2;
                // 滚动更新
                dp_i_2 = dp_i_1;
                dp_i_1 = dp_i;
            }
            return dp_i_1;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new _509_FibonacciNumber().new Solution();
        System.out.println(solution.fib1(5));
        System.out.println(solution.fib(5));
        System.out.println(solution.fib3(5));
        System.out.println(solution.fib4(5));
    }
}
